package com.lx.algorithm.code.xly3.class03;

import com.lx.algorithm.Utils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

import static com.lx.algorithm.Utils.*;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-05 00:54:56
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-05     张李鑫                     1.0         1.0 Version
 */
public class Code06 {
    /**
     * 给定一个由字符串组成的数组String[] strs，给定一个正数K
     * <p>
     * 返回词频最大的前K个字符串，假设结果是唯一的
     */

    public static class Info {
        int count;
        String str;

        public Info(int count, String str) {
            this.count = count;
            this.str = str;
        }
    }

    public static String topK(String[] strs, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            if (map.containsKey(strs[i])) {
                map.put(strs[i], map.get(strs[i]) + 1);
            } else {
                map.put(strs[i], 1);
            }
        }
        Info[] arr = new Info[map.size()];

        int i = 0;
        Set<Map.Entry<String, Integer>> entries = map.entrySet();

        for (Map.Entry<String, Integer> entry : entries) {
            arr[i++] = new Info(entry.getValue(), entry.getKey());
        }

        Info minKth = getMinKth(arr, arr.length-k+1);
        return minKth.str;
    }

    public static void main(String[] args) {
        String[] arr1 = { "A", "B", "A", "C", "A", "C", "B", "B", "K" };
        System.out.println(topK(arr1, 2));
        System.out.println(123);
    }

    private static Info getMinKth(Info[] ints, int i) {
        int l = 0;
        int r = ints.length - 1;
        int[] range = null;
        while (l < r) {
            Info rd = ints[r];
            range = partition(ints, l, r, rd);
            if (i > range[1]) {
                l = range[1] + 1;
            } else if (i < range[0]) {
                r = range[0] - 1;
            } else {
                return rd;
            }
        }
        return ints[l];
    }

    public static int[] partition(Info[] arr, int L, int R, Info pivot) {
        int less = L - 1;
        int more = R + 1;
        while (L < more) {
            if (arr[L].count < pivot.count) {
                swap(arr, L++, ++less);
            } else if (arr[L].count > pivot.count) {
                swap(arr, --more, L);
            } else {
                L++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    public static void swap(Info[] arr, int j, int i) {
        Info swap = arr[j];
        arr[j] = arr[i];
        arr[i] = swap;
    }


    public static int[] partition(int[] arr, int L, int R, int pivot) {
        int less = L - 1;
        int more = R + 1;
        while (L < more) {
            if (arr[L] < pivot) {
                Utils.swap(arr, L++, ++less);
            } else if (arr[L] > pivot) {
                Utils.swap(arr, --more, L);
            } else {
                L++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    /**
     * 改写快排的方式
     * 把大于放右边小于放左边找命中区 命中区是否在i以内 如果在 就是命中区的数字
     *
     * @param ints
     * @param i
     * @return
     */
    private static int getMinKth(int[] ints, int i) {
        int l = 0;
        int r = ints.length - 1;
        int[] range = null;
        while (l < r) {
            int rd = ints[r];
            range = partition(ints, l, r, rd);
            if (i > range[1]) {
                l = range[1] + 1;
            } else if (i < range[0]) {
                r = range[0] - 1;
            } else {
                return rd;
            }
        }
        return ints[l];
    }
}